class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
public class demo1 {
    public void reorderList(ListNode head) {
        //处理边界情况
        if(head==null||head.next==null||head.next.next==null)return;
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        // 把slow后面的部分给逆序 - 头插
        ListNode head2=new  ListNode();
        ListNode cur=slow.next;
        slow.next=null;//将两个链表分离
        while(cur!=null){
            ListNode ncur=cur.next;
            cur.next=head2.next;
            head2.next=cur;//使用head2.next指向cur
            cur=ncur;
        }
        //合并两个链表
        ListNode cut=head, cut2=head2.next;
        ListNode ret=new ListNode();
        ListNode newprve=ret;
        while(cut!=null){
            newprve.next=cut;
            newprve=cut;
            cut=cut.next;
            if(cut2!=null){
                newprve.next=cut2;
                newprve=cut2;
                cut2=cut2.next;
            }
        }
    }
}
